﻿#include <iostream>

#define G 'G'
#define R 'R'
#define MIN(a, b) (a < b ? a : b)

static int preprocessing(const char* text)
{
	if (!text) return 0;

	auto size = strlen(text);
	if (size <= 1) return 0;

	// 每个位置的左侧有多少个G
	// eg. R G R G R
	//    | | | | | |
	int* leftGArr = (int*)malloc((size + 1) * sizeof(int));
	memset(leftGArr, 0, (size + 1) * sizeof(int));
	int leftGExists = 0;
	for (int leftEdge = 1; leftEdge <= size; leftEdge++)
	{
		if (text[leftEdge - 1] == G)
		{
			++leftGExists;
		}

		leftGArr[leftEdge] = leftGExists;
	}

	// 每个位置右侧有多少个R
	int* rightRArr = (int*)malloc((size + 1) * sizeof(int));
	memset(rightRArr, 0, (size + 1) * sizeof(int));
	int rightRExists = 0;
	for (int rightEdge = size - 1; rightEdge >= 0; rightEdge--)
	{
		if (text[rightEdge] == R)
		{
			++rightRExists;
		}

		rightRArr[rightEdge] = rightRExists;
	}

	int changeTimes;
	int minChangeTimes = size;
	for (int leftEdge = 0; leftEdge <= size; leftEdge++)
	{
		if (leftEdge == 0)
		{
			changeTimes = rightRArr[leftEdge];
		}
		else if (leftEdge == size)
		{
			changeTimes = leftGArr[leftEdge];
		}
		else
		{
			changeTimes = leftGArr[leftEdge] + rightRArr[leftEdge];
		}

		minChangeTimes = MIN(minChangeTimes, changeTimes);
	}

	free(leftGArr);
	free(rightRArr);

	return minChangeTimes;
}

/**
 * 牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色，
 * 这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后，每个红色R都比每个绿色G距离最左侧近。
 * 牛牛想知道他最少需要涂染几个正方形。
 * 如样例所示: s=RGRGR
 * 我们涂染之后变成RRRGG满足要求了，涂染的个数为2，没有比这个更好的涂染方案。
 *
 * 可以理解为R的左侧不能出现G, 即要达成的效果是：R都在左侧，G都在右侧、
 *
 * 方案1: 左侧有0个正方形，右侧有5个正方形
 * _ | RGRGR, 左侧不动，因为没有正方形；右侧将3个R改为G；改动量：3
 *
 * 方案2: 左侧有1个正方形，右侧有4个正方形
 * R | GRGR, 左侧不动，因为已经都是R了；右侧将2个R改为G；改动量：2
 *
 * 方案3: 左侧有2个正方形，右侧有3个正方形
 * RG | RGR, 左侧改一个G；右侧将2个R改为G；改动量：3
 *
 * 方案4: 左侧有3个正方形，右侧有2个
 * RGR | GR, 左侧改一个G；右侧改一个R；改动量：2
 *
 * 方案5: 左侧有4个正方形，右侧有1个
 * RGRG | R, 左侧改2个G；右侧改一个R；改动量：3
 *
 * 方案6: 左侧有5个正方形，右侧有0个
 * RGRGR | _, 左侧改2个G；右侧不动；改动量：2
 *
 * ∴最优解：改动2次
 */
int main_PaintSquare()
{
	char text[200] = "GRRGGRGRGGGRRRRG";
	int minChangeTimes = preprocessing(text);
	printf("%d", minChangeTimes);
	return 0;
}